#include <stdio.h>

#define NotAVertex (-1)
typedef int TwoDimArray[4][4];

/* START: fig10_53.txt */
/* Compute All-Shortest Paths */
/* A[ ] contains the adjacency matrix */
/* with A[ i ][ i ] presumed to be zero */
/* D[ ] contains the values of the shortest path */
/* N is the number of vertices */
/* A negative cycle exists iff */
/* D[ i ][ i ] is set to a negative value */
/* Actual path can be computed using Path[ ] */
/* All arrays are indexed starting at 0 */
/* NotAVertex is -1 */

void AllPairs(TwoDimArray A, TwoDimArray D, TwoDimArray Path, int N) {
	int i, j, k;

	/* Initialize D and Path */
	/* 1*/for (i = 0; i < N; i++)
		/* 2*/for (j = 0; j < N; j++) {
			/* 3*/D[i][j] = A[i][j];
			/* 4*/Path[i][j] = NotAVertex;
		}

	/* 5*/for (k = 0; k < N; k++)
		/* Conider each vertex as an intermediate */
		/* 6*/for (i = 0; i < N; i++)
			/* 7*/for (j = 0; j < N; j++)
				/* 8*/if (D[i][k] + D[k][j] < D[i][j]) {
					/* Update shortest path */
					/* 9*/D[i][j] = D[i][k] + D[k][j];
					/*10*/Path[i][j] = k;
				}
}
/* END */

main() {
	TwoDimArray A = { { 0, 2, -2, 2 }, { 1000, 0, -3, 1000 },
			{ 4, 1000, 0, 1000 }, { 1000, -2, 3, 0 } };
	TwoDimArray D, Path;
	int i, j;

	AllPairs(A, D, Path, 4);
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++)
			printf("%6d ", D[i][j]);
		printf("\n");
	}

	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++)
			printf("%6d ", Path[i][j]);
		printf("\n");
	}

	return 0;
}
